using namespace std;
const long ASIZE = 500000L;

//----------------------------------------------------
#include <iostream>
#include <cstdio> // snprintf()
#include <cstdlib> // RAND_MAX
#include <cstring> // strlen(), memcpy()
#include <string>

using std::cin;
using std::cout;
using std::string;

// 以下 MyString 是为了测试 containers with moveable elements 效果。
class MyString {
public:
    // typedef unsigned long long size_t
    static size_t DCtor; // default-ctor 调用次数
    static size_t Ctor; // ctor 调用次数
    static size_t CCtor; // copy-ctor 调用次数
    static size_t CAsgn; // copy-asgn 调用次数
    static size_t MCtor; // move-ctor 调用次数
    static size_t MAsgn; // move-asgn 调用次数
    static size_t Dtor; // dtor 调用次数

private:
    char* _data;
    size_t _len;

    void _init_data(const char* s) {
        _data = new char[_len + 1];
        memcpy(_data, s, _len);
        _data[_len] = '\0';
    }

public:
    // default ctor
    MyString() : _data(NULL), _len(0) { ++DCtor; }

    // ctor
    MyString(const char* p) : _len(strlen(p)) {
        ++Ctor;
        _init_data(p); // COPY
    }

    // move ctor, with "noexcept"，移动构造函数
    MyString(MyString&& str) noexcept : _data(str._data), _len(str._len) {
        ++MCtor;
        str._len = 0;
        str._data = NULL; // 避免delete (in dtor)
    }

    // copy assignment
    MyString& operator=(const MyString& str) {
        ++CAsgn;
        if (this != &str) {
            if (_data) {
                delete _data;
                _len = str._len;
                _init_data(str._data); // COPY
            }
        } else {
            // Self Assignment, Nothing to do.
        }
        return *this;
    }

    // move assignment
    MyString& operator=(MyString&& str) noexcept {
        ++MAsgn;
        if (this != &str) {
            if (_data) {
                delete _data;
            }
            _len = str._len;
            _data = str._data; // MOVE
            str._len = 0;
            str._data = NULL; // 避免 deleted in dtor
        }
        return *this;
    }

    // dtor
    virtual ~MyString() {
        ++Dtor;
        if (_data) {
            delete _data;
        }
    }

    // 为了让 set 比较大小
    bool operator<(const MyString& rhs) const {
        // 借用事实：string 已能比较大小
        return std::string(this->_data) < std::string(rhs._data);
    }

    // 为了让 set 判断相等
    bool operator==(const MyString& rhs) const {
        // string 已能判断相等
        return std::string(this->_data) == std::string(rhs._data);
    }

    char* get() const {
        return _data;
    }
};

size_t MyString::DCtor = 0;
size_t MyString::Ctor=0;  	 
size_t MyString::CCtor=0;
size_t MyString::CAsgn=0;
size_t MyString::MCtor=0;
size_t MyString::MAsgn=0;
size_t MyString::Dtor=0;

// 必须放在 std 内 ？？？
namespace std {
template<> struct hash<MyString> {
    size_t operator()(const MyString& s) const noexcept {
        // 借用现有的 hash<string> (in ...\include\c++\bits\basic_string.h)
        return hash<string>()(string(s.get()));
    }
};
}

//----------------------------------------------------
// 以下 MyStrNoMove 是为了测试 containers with no-moveable elements 效果。
class MyStrNoMove { 
public: 
    static size_t DCtor;  	//累計 default-ctor 的呼叫次數 
    static size_t Ctor;  	//累計 ctor      的呼叫次數 
    static size_t CCtor;  	//累計 copy-ctor 的呼叫次數 
    static size_t CAsgn;  	//累計 copy-asgn 的呼叫次數 
    static size_t MCtor;  	//累計 move-ctor 的呼叫次數 
    static size_t MAsgn;  	//累計 move-asgn 的呼叫次數 		    
    static size_t Dtor;	    //累計 dtor 的呼叫次數 
private:     
  	char* _data; 
  	size_t _len; 
  	void _init_data(const char *s) { 
    		_data = new char[_len+1]; 
    		memcpy(_data, s, _len); 
    		_data[_len] = '\0'; 
  	} 
public: 
	//default ctor
  	MyStrNoMove() : _data(NULL), _len(0) { 	++DCtor; _init_data("liushibo"); }

	//ctor
  	MyStrNoMove(const char* p) : _len(strlen(p)) { 
    	++Ctor;  _init_data(p); 
  	} 

	// copy ctor
  	MyStrNoMove(const MyStrNoMove& str) : _len(str._len) { 
		++CCtor;  	 
    	_init_data(str._data); 	//COPY
  	} 

 	//copy assignment
  	MyStrNoMove& operator=(const MyStrNoMove& str) { 
    	++CAsgn;

		if (this != &str) { 
    		if (_data) delete _data;  
      		_len = str._len; 
      		_init_data(str._data); 	//COPY! 
    	} 
    	else {
		    // Self Assignment, Nothing to do.   
		}
    	return *this; 
  	} 

 	//dtor
  	virtual ~MyStrNoMove() { 	   
  	    ++Dtor;		  	    
    	if (_data) {
    		delete _data; 	
		}
  	}   	
  	
  	bool 											
  	operator<(const MyStrNoMove& rhs) const		//為了讓 set 比較大小 
  	{
	   return string(this->_data) < string(rhs._data);  //借用事實：string 已能比較大小. 
	}  	
	
  	bool 											
  	operator==(const MyStrNoMove& rhs) const	//為了讓 set 判斷相等. 
  	{
	   return string(this->_data) == string(rhs._data);  //借用事實：string 已能判斷相等. 
	} 
		
	char* get() const { return _data; }	
}; 
size_t MyStrNoMove::DCtor=0;  	
size_t MyStrNoMove::Ctor=0;  
size_t MyStrNoMove::CCtor=0;
size_t MyStrNoMove::CAsgn=0;
size_t MyStrNoMove::MCtor=0;
size_t MyStrNoMove::MAsgn=0;
size_t MyStrNoMove::Dtor=0;

namespace std 	//必須放在 std 內 
{
template<> 
struct hash<MyStrNoMove> 	//這是為了 unordered containers 
{
	size_t 
	operator()(const MyStrNoMove& s) const noexcept
	{  return hash<string>()(string(s.get()));  }  
	   //借用現有的 hash<string> (in ...\4.9.2\include\c++\bits\basic_string.h)
};
}


//----------------------------------------------------
#include <iostream>
#include <cstdio> // snprintf()，转换成字符串
#include <cstdlib> // RAND_MAX
#include <string>
#include <algorithm>
#include <list>
#include <forward_list>

using std::cin;
using std::cout;
using std::string;
using std::max;
using std::min;

namespace stl00 {
bool strLonger(const string& s1, const string& s2) {
    return s1.size() < s2.size();
}

void test_misc() {
    
}

}

//--------------------------------------------------- 264
#include <typeinfo> // typeid
template<typename T>
void output_static_data(const T& myStr) {
    cout << typeid(myStr).name() << "--" << endl;
	cout << " CCtor = " << T::CCtor 	
		 << " MCtor = " << T::MCtor 
	     << " CAsgn = " << T::CAsgn 		 
		 << " MAsgn = " << T::MAsgn 
		 << " Dtor = "  << T::Dtor 
		 << " Ctor = "  << T::Ctor 
		 << " DCtor = " << T::DCtor 		 
		 << endl;	
}

#include <ctime> // clock_t, clock()


//--------------------------------------------------- 341
long get_a_target_long() {
    long target = 0;
    cout << "target (0~" << RAND_MAX << "): ";
    cin >> target;
    return target;
}

string get_a_target_string() {
    long target = 0;
    char buf[10];
    cout << "target (0~" << RAND_MAX << "): ";
    cin >> target;
    // snprintf函数是一个用于格式化输出到字符串的函数，可以将格式化后的内容写入指定大小的字符数组中。
    // int snprintf(char* str要写入内容的字符数组指针, size目标字符数组大小, format格式化字符串, ...可变数量的参数来替换格式化字符串中的占位符)
    snprintf(buf, 10, "%d", target);
    return string(buf);
}

int compareLongs(const void* a, const void* b) {
    return (*(long*)a - *(long*)b);
}

int compareStrings(const void* a, const void* b) {
    if (*(string*)a > *(string*)b) {
        return 1;
    } else if (*(string*)a < *(string*)b) {
        return -1;
    } else {
        return 0;
    }
}

// --------------------------------------------------- 376 array
#include <array>
#include <iostream>
#include <ctime>
#include <cstdlib> // qsort, bsearch, NULL

namespace stl01 {
void test_array() {
    cout << "\ntest_array..................." << endl;

    array<long, ASIZE> c;
    clock_t timeStart = clock();
    for (long i = 0; i < ASIZE; ++i) {
        c[i] = rand();
    }
    cout << "milli-seconds: " << (clock() - timeStart) << endl;
    cout << "array.size() = " << c.size() << endl;
    cout << "array.front() = " << c.front() << endl;
    cout << "array.back() = " << c.back() << endl;
    // data() 返回指向数组首元素的指针
    cout << "array.data() = " << c.data() << endl;

    long target = get_a_target_long();

    timeStart = clock();
    // ::qsort() 是全局的qsort()
    ::qsort(c.data(), ASIZE, sizeof(long), compareLongs);
    long* pItem = (long*)::bsearch(&target, c.data(), ASIZE, sizeof(long), compareLongs);
    cout << "qsort() + bsearch(), milli-seconds: " << (clock() - timeStart) << endl;
    if (pItem != NULL) 
        cout << "found: " << *pItem << endl;
    else 
        cout << "not found!" << endl; 
}
}

//--------------------------------------------------- 412 vector
#include <vector>
#include <stdexcept> // 处理异常
#include <string>
#include <cstdlib> // abort() 
#include <cstdio> // snprintf()
#include <iostream>
#include <ctime>
#include <algorithm> // sort()
namespace stl02 {
void test_vector(long& value) {
    cout << "\ntest_vector()................." << endl;
    vector<string> c;
    char buf[10];
    clock_t timeStart = clock();
    for (long i = 0; i < value; ++i) {
        try { // 防止内存不够用
            snprintf(buf, 10, "%d", rand());
            c.push_back(string(buf));
        } catch (exception& p) {
            // 试试最高 i 到多少会出现 then std::bad_alloc
            cout << "i = " << i << " " << p.what() << endl;
            // 当调用 abort() 函数时，程序会立即停止执行，并生成一个异常终止信号，通常会导致程序退出并产生一个核心转储文件（core dump）。
            abort();
        }
    }
	cout << "milli-seconds: " << (clock()-timeStart) << endl;	
	cout << "vector.max_size() = " << c.max_size() << endl;	// 1073747823
	cout << "vector.size() = " << c.size() << endl;		
	cout << "vector.front() = " << c.front() << endl;	
	cout << "vector.back() = " << c.back() << endl;	
	cout << "vector.data() = " << c.data() << endl;
	cout << "vector.capacity() = " << c.capacity() << endl << endl;	
    
    string target = get_a_target_string();
    {
        timeStart = clock();
        // :: 表全局，在本作用域找不到就回去全局寻找
        auto pItem = ::find(c.begin(), c.end(), target);
        cout << "std::find(), milli-seconds: " << (clock() - timeStart) << endl;
        if (pItem != c.end())
            cout << "found: " << *pItem << endl;
        else 
            cout << "not found!" << endl << endl;
    }
    
    {
        timeStart = clock();
        sort(c.begin(), c.end());
        cout << "sort(), milli-seconds: " << (clock() - timeStart) << endl;

        timeStart = clock();
        string* pItem = (string*)::bsearch(&target, c.data(), c.size(), sizeof(string), compareStrings);
        cout << "bsearch(), milli-seconds: " << (clock() - timeStart) << endl;
         if (pItem != NULL)
            cout << "found: " << *pItem << endl;
        else 
            cout << "not found!" << endl << endl;

        c.clear();
	    // test_moveable(vector<MyString>(),vector<MyStrNoMove>(), value);	
    }
}
}

//--------------------------------------------------- 589 

//--------------------------------------------------- 1764 
#include <iostream>
#include <algorithm>
#include <vector>
namespace stl36 {
bool myfunc(int i, int j) { return i < j; }

}


//---------------------------------------------------
#include <cstdlib> // rand() and RAND_MAX
int main(int argc, char const *argv[]) {
    
    return 0;
}


/**
C++ 体系结构与内核分析
*/